This invention relates to methods of Connection Admission Control (CAC) in packetized communication networks. More particularly, the invention relates to CAC in networks that apply the Earliest-Deadline-First (EDF) scheduling discipline.
FIG. 1 schematically depicts a simplified packet network in which users 10.1-10.3, 12.1-12.4, and 15.1-15.3 can intercommunicate via interconnected servers or switches 20.1-20.5. The network has been simplified for illustrative purposes; real-life networks will typically have many more users and servers than shown in the figure. If, e.g., user 10.1 wishes to reach user 15.1 through the network, user 10.1 will issue a request to its associated server 20.1 to set-up a session. A session is a collection of related packets having a fixed path from a source to a destination, and having a specified description of properties such as packet-injection rate, burst size, and maximum packet length. The fixed path will typically be determined when the user makes the set-up request, and may be determined by the first server 20.1. The set-up request is passed to every server along the path. Each server engages a function, referred to as Connection Admission Control (CAC), which determines whether to admit the requested session. If the session is admitted by every server along the path, the set-up request is honored and the packets can be sent.
Each server e has a finite processing rate Ce. That is, each server e can relay its queued packets to the next server (or from the last server to the destination user) at a rate no greater than Ce bits per unit time. Because this processing rate is finite, some bits will generally accrue delay at some or all of the servers along the path.
Excessive packet delay may be intolerable to customers of various kinds of network traffic, such as voice traffic, which is notoriously delay-sensitive. It is of increasing interest to specify, inter alia, the delay performance demanded of a network under the rubric of Quality of Service (QoS) requirements. In this regard, a typical QoS requirement is that packet delay in a specified class of service must always be less than a specified threshold, or (if it is a probabilistic requirement) that there must be no more than a specified probability that packet delay will exceed the threshold.
In networks subject to QoS requirements, the CAC function will consider whether the specified limits on delay can be met. If it is determined that the specified limits cannot be met, the offered session will be denied admission. Whether these limits can be met will depend, in part, on how the resources of the server are allocated among sessions. (It should be noted that the term xe2x80x9csessionxe2x80x9d as used herein is synonymous with the term xe2x80x9cconnectionxe2x80x9d in the sense that would apply in the present context.) Such allocations are governed by so-called scheduling disciplines. Two prominent scheduling disciplines are those known as Generalized Processor Sharing (GPS) and Earliest-Deadline-First (EDF). Under GPS, the server partitions its resources among connections according to specified weights. Under EDF, the server assigns a deadline dp to each incoming packet p upon arrival, and then always serves the packet with the earliest deadline. For a given network state, each scheduling discipline may lead to a different decision regarding the admissibility of a newly offered session.
Most approaches to the delay-based admission decision have relied on worst-case assumptions, e.g., that all sessions will simultaneously send a burst of packets at the peak arrival rate. Approaches that rely on such assumptions are disadvantageous because they will deny admission to an excessive number of calls. Some improvement in the amount of carried traffic has been achieved, at least exploratorily, through the approach known as statistical multiplexing, which takes advantage of the statistical nature of the offered traffic in order to accept more offered sessions while adhering to probabilistic delay bounds. Discussions of statistical multiplexing as applied to GPS scheduling can be found, for example, in A. Elwalid et al., xe2x80x9cDesign of generalized processor sharing schedulers which statistically multiplex heterogeneous QoS classes,xe2x80x9d Proc. IEEE INFOCOM ""99 (March 1999) 1220-1230, and in K. Kumaran et al., xe2x80x9cNovel techniques for the design and control of Generalized Processor Sharing schedulers for multiple QoS classes,xe2x80x9d submitted for publication in Proc. IEEE INFOCOM ""00, (March 2000).
Until now, however, there has been no application of statistical multiplexing to delay-based admission decisions under the EDF scheduling discipline.
I have developed a new method for estimating the probability of violating a packet-delay bound under the EDF scheduling discipline. My method takes into account the statistical properties of offered network traffic, and thus comes under the scope of statistical multiplexing. My method will make it possible for a server employing EDF to satisfy probabilistic QoS requirements while admitting many more offered sessions than possible using the older CAC methods that rely on worst-case assumptions about the offered traffic.
Thus, in one aspect, my invention involves a method for determining the admissibility of an offered session of traffic of a specified class to a server in a packetized communication network. Each class c has a peak traffic rate r(c). The server has a total processing rate C. Admitted packets are scheduled according to an EDF scheduling discipline. The method for determining admissibility comprises defining an operating point for the server. The operating point represents the number of sessions Nc of each respective class currently offered or currently being served. The method further comprises determining whether the defined operating point falls within a set of operating points that together define an admissible region. The admissible region consists of operating points for which the probability of violating a delay bound for any packet is below a threshold. In contrast to methods of the prior art, the admissible region includes at least one point that would lead to violations of the packet-delay bound if all sessions were to simultaneously start sending a burst of packets at the peak arrival rate.